﻿#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

static int convertToNumber(const char* templateStr, const char* code)
{
	size_t templateSize = strlen(templateStr);
	unordered_map<char, int> templateDic;
	char cur;

	for (int i = 1; i <= templateSize; i++)
	{
		cur = templateStr[i - 1];
		templateDic[cur] = i;
	}

	size_t codeSize = strlen(code);
	int base;
	int num = 0;
	for (int i = codeSize - 1; i >= 0; i--)
	{
		cur = code[i];
		base = templateDic[cur];
		num += base * (int)pow(templateSize, codeSize - 1 - i);
	}

	return num;
}

static string convertToCode(const char* templateStr, const int targetNumber)
{
	size_t templateSize = strlen(templateStr);
	double pw = log(targetNumber) / log(templateSize);
	int iPw = (int)pw;
	int total = 0;
	int base;

	for (int i = iPw; i >= 0 ; i--)
	{
		base = pow(templateSize, i);
		total += base * 1;
	}

	if (targetNumber < total)
	{
		--iPw;
	}

	int* numbersInEveryPosition = (int*)malloc(sizeof(int) * (iPw + 1));
	memset(numbersInEveryPosition, 0, sizeof(int) * (iPw + 1));
	total = targetNumber;
	for (int i = 0; i <= iPw; i++)
	{
		numbersInEveryPosition[i] = 1;
		base = pow(templateSize, i);
		total -= base;
	}

	int n;
	for (int i = iPw; i >= 0; i--)
	{
		base = pow(templateSize, i);
		n = total / base;
		numbersInEveryPosition[i] += n;
		total -= base * n;

		if (total == 0) break;
	}

	char str[100] = { 0 };
	int index = 0;
	for (int i = iPw; i >= 0; i--)
	{
		str[index++] = templateStr[numbersInEveryPosition[i] - 1];
	}

	free(numbersInEveryPosition);

	string code = str;
	return code;
}

/**
 * 一个char类型的数组chs，其中所有的字符都不同。
 * 例如: chs=['A','B','C',...'Z'], 则字符串与整数的对应关系如下：
 * A,B,...,Z,AA,AB,...,AZ,BA,BB,...,ZZ,AAA,...,ZZZ,AAAA,...
 * 1,2,...,26,27,28,...,52,53,54,...,702,703,...,18278,18279,...
 * 例如，chs=['A','B','C'], 则字符串与整数的对应关系如下：
 * A,B,C,AA,AB,...,CC,AAA,...,CCC,AAAA,...
 * 1,2,3,4,5,...,12,13,...,39,40...
 * 给定一个数组chs，实现根据对应关系完成字符串与整数相互转换的两个函数。
 * 
 * 思路：
 * 伪进制，数字是不带0的，比如伪3进制，将一个正整数分解为:
 * N = n0*3^0+n1*3^1+n2*3^2+n3*3^3+...
 * 其中，从n0到nk都是正整数，中间是不存在0的
 * 
 * 举例:
 * 9 = 3*3^0+2*3^1 => 23
 * 
 * 基本思路是，先看最高位能填到哪一位，但是又不能让低位填0，故从能填到的最高位往最低位先依次填1，然后再从高位到低位，将数字补满.
 * 
 * 举例:
 * 9最高可以填写到3*3^2, 但是如果这样填写，那么3^0和3^1都得填0了，故不能直接填写3^2这一位。
 * 先将3^0和3^1这两位都填1，然后，剩余9-1*3^1-1*3^0=5, 3^1再+1，剩余2，3^0再+2，即为23.
 */
int main_pseudoNSystem()
{
	auto str = convertToCode("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 52);
	printf("str=%s\n", str.c_str());
	auto num = convertToNumber("ABCDEFGHIJKLMNOPQRSTUVWXYZ", "ZZZ");
	printf("num=%d\n", num);
	return 0;
}